package com.linchong.linkedlist.medium;

import com.linchong.linkedlist.basic.BasicLinkList;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-30 22:55
 * @Description: DetectCycle$
 *
 * 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 *
 * 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
 *
 * 说明：不允许修改给定的链表。
 *
 * 进阶：
 *
 * 你是否可以使用 O(1) 空间解决此题？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/linked-list-cycle-ii
 *  a+b+c+b = 2(a+b)
 *  a:环之前
 *  b:慢指针走到
 *  c:相遇后，相遇点到环入口的距离
 *
 */
public class DetectCycle extends BasicLinkList {

	public ListNode detectCycle(ListNode head) {
		if(head == null){
			return null;
		}

		ListNode slow = head;
		ListNode fast = head;
		while(fast.next !=null){
			slow = slow.next;
			fast = fast.next.next;
			if(fast == null){
				return null;
			}
			if(slow == fast){
				slow = head;
				while(slow!=fast){
					slow = slow.next;
					fast = fast.next;
				}
				return slow;
			}
		}
		return null;
	}

}
